package leetcode.pre100;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 给出一个区间的集合，请合并所有重叠的区间。
 *
 * 示例 1:
 *
 * 输入: [[1,3],[2,6],[8,10],[15,18]]
 * 输出: [[1,6],[8,10],[15,18]]
 * 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * 示例 2:
 *
 * 输入: [[1,4],[4,5]]
 * 输出: [[1,5]]
 * 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
 *
 *  一个一个遍历，用list存储。list存储的是int[]区间。
 * 区间合并[a,b],[c,d] 满足b>=c  然后比较b和d大小
 * @date 2020/4/5 16:53
 */
public class Code56_MergeRange_合并区间 {
    public static void main(String[] args) {
        int[][] ints = {{1,3},{2,6},{8,10},{15,18}};
        int[][] merge = merge(ints);
        for (int[] ints1 : merge) {
            System.out.println(Arrays.toString(ints1));
        }
    }
    public static int[][] merge(int[][] intervals) {
        if(intervals == null || intervals.length == 0 || intervals[0].length == 0)
            return new int[0][0];
        //先按照第一个元素排序
        Arrays.sort(intervals,(int1,int2)->
                int1[0] == int2[0] ? int1[1] - int2[1] : int1[0] - int2[0]);
        //区间合并[a,b],[c,d] 满足b>=c  然后比较b和d大小
        LinkedList<int[]> list = new LinkedList<>();
        list.add(new int[]{intervals[0][0],intervals[0][1]});
        for (int i = 1; i < intervals.length ; i++) {
            //[a,b],[c,d] b>=c 合并，看b和d大小
            if(intervals[i][0] <= list.getLast()[1]){
                list.getLast()[1] = Math.max(list.getLast()[1],intervals[i][1]);
            }else {
                list.add(intervals[i]);
            }
        }
        return list.toArray(new int[0][0]);
    }
}
